package arithmetic.LeetCode.Array_Partition_I;

/**
 * @author zhangyanqi
 * @since 1.0 2017/10/10
 */
class Solution {

    public int arrayPairSum(int[] nums) {
        quickSort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 1; i = i + 2) {
            sum += nums[i];
        }
        return sum;
    }


    public static void quickSort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    /**
     * 分治
     *
     * @param array
     * @param begin
     * @param end
     */
    public static void sort(int[] array, int begin, int end) {
        int position = getPosition(array, begin, end);
        if (position - 1 >= begin) {
            sort(array, begin, position - 1);
        }
        if (position + 1 <= end) {
            sort(array, position + 1, end);
        }
    }

    /**
     * 设置最后一个数为基准,算出最后一个数应该在分区中的位置，并把比他小的数放进左侧，比他大的书放进右侧
     *
     * @param array
     * @param begin 开始的下标
     * @param end   结束的下标
     * @return
     */
    public static int getPosition(int[] array, int begin, int end) {
        int storeIndex = begin;
        int pivot = array[end];
        for (int i = begin; i <= end; i++) {
            while (array[storeIndex] <= pivot && storeIndex < end) {
                storeIndex++;
                if (i < storeIndex) {
                    i = storeIndex;
                }
            }
            if (storeIndex == end) {
                return end;
            }
            if (array[storeIndex] >= pivot && array[i] <= pivot) {
                changePosition(array, i, storeIndex);
                if (i != end) {
                    storeIndex++;
                }
            }
        }
        return storeIndex;
    }

    /**
     * 交换两个数的位置
     *
     * @param array
     * @param indexA
     * @param indexB
     */

    public static void changePosition(int[] array, int indexA, int indexB) {
        if (array.length < indexA - 1 || array.length < indexB - 1 || indexA < 0 || indexB < 0) {
            throw new IllegalStateException("下标错误");
        }
        int temp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = temp;
    }

}
